Embodiments of this invention relate to the subject of arbitration in electronic circuits, and particularly to arbitration in asynchronous systems.
Because events in asynchronous systems may occur at any time, it is often necessary to choose an action that depends on which of two, or more, sometimes nearly simultaneous events is to be treated first. Devices that make such choices are commonly called arbiters. Arbiters are often used in situations where most of the time the two input events arrive with a relatively large time separation, and it is then easy to make a clean decision as to which event arrived firstxe2x80x94we call this situation xe2x80x9can uncontested input requestxe2x80x9d. Only infrequently do the two input requests arrive nearly simultaneously, and it is in these circumstances that the arbiter really has to work for a living and make a clean decision as to which input has arrived first.
A block diagram of a typical arbiter is shown in FIGS. 1A and 1B. The arbiter of FIG. 1A has five terminals and is therefore sometimes called a xe2x80x9cfive-wirexe2x80x9d arbiter. It is often used to sequence events and so is frequently called a xe2x80x9cSequencer arbiterxe2x80x9d or xe2x80x9cSequencerxe2x80x9d. The Sequencer arbiter receives signals on the two request inputs R1, R2 and issues signals on the two grant outputs G1, G2. The arbiter also receives signals on the xe2x80x9cDonexe2x80x9d input D.
Many different encodings of the input and output signals of arbiters are possible. For example, each rising transition of an electrical voltage on a wire might be used to signal the event. The signal could also be encoded as a falling transition, or any other change in a voltage, current, light level or similar phenomena. Electrical or other forms of pulses may also be used to encode events.
However the signal is encoded, the arbiter monitors the request inputs and, when a signal is received on one request input, the arbiter sends a signal on the corresponding grant output, unless a grant is already outstanding. A grant is outstanding when one grant signal has been issued but a Done signal has not been received. Where two request signals are received substantially simultaneously, the arbiter unambiguously chooses one of the requests and issues a grant signal on the grant output corresponding to the chosen request. When a Done signal is received, a grant for the unchosen request is issued.
In this way, an arbiter can arbitrate contending accesses to a resource. Two principal forms of arbiter known in the art are the Sequencer arbiter and the RGD arbiter.
The first form of prior art arbiter, the Sequencer arbiter, mentioned above is sometimes also called a xe2x80x9cSequencerxe2x80x9d. The communication channel between the Sequencer arbiter and each of its users has a pair of event signals called Request and Grant, and a common Done event signal is shared by all of the users. For two channels, a Sequencer arbiter has five connections and is sometimes referred to as a xe2x80x9cfive-wirexe2x80x9d arbiter, as explained above. A typical Sequencer arbiter is shown in FIG. 1A. Herein we refer to the five event signals of a Sequencer arbiter as R1, G1, R2, G2 and D.
The second form of prior art arbiter is the Request, Grant, Done (RGD) arbiter. As its name implies, the communication channel between the RGD arbiter and each of its users has three event signals called Request, Grant and Done, on each of its channels. An RGD arbiter that arbitrates among two channels will have six event signals, three for the first channel of communication (R1, G1, D1), and three for the second channel of communications (R2, G2, D2). The numerical designation identifies the communication channel, and thus the user.
The dot by the D input in FIG. 1A is used to indicate the initial state of the arbiter and signifies that the arbiter is initialized as if an input has been received on the D input.
FIG. 1B shows an RGD arbiter. The dot between the D1 and D2 inputs indicates that the arbiter is initialized as if a Done input event has been received on either input D1 or input D2, and that upon the receipt of a request input the arbiter can issue a grant signal.
For both types of arbitersxe2x80x94Sequencer arbiters and RGD arbitersxe2x80x94the request event signals (R1 and R2) and Done event signals (D or D1 and D2) are input signals, while the grant event signals (G1 and G2) are output signals.
The arbiter action in both the above prior art arbiters controls when the arbiter will issue grant signals. The intent of arbitration implies that the arbiter will issue only one grant signal xe2x80x9cat a time.xe2x80x9d In asynchronous systems, however, the notion of xe2x80x9cat a timexe2x80x9d must be made more explicit. For the RGD arbiter the conventional rule is that after issuing a grant signal G1 in response to a request R1, the arbiter will issue no further grant signals, G1 or G2, until it receives the Done signal D1. The Done signal indicates that whatever action was to occur on that first channel is complete. Thus for the RGD arbiter, after a first request R1 on channel 1, and after that channel is given a grant G1, a following request on channel 1 or a request on channel 2 the arbiter must wait for the Done signal D1 before the arbiter can issue a grant signal, either a G1 or a G2 respectively. This second grant signal is delayed until channel 1 has finished its action in response to the first grant signal on channel 1 and so indicated via the Done signal D1. For the Sequencer arbiter the rule is similar. In the Sequencer arbiter, however, both channels indicate completion with the same common Done signal D. Because only one channel can have an outstanding grant, there is no ambiguity, upon receipt of a Done signal D, regarding which channel indicated a completion.
The Sequencer arbiter and the RGD arbiter are closely related. It is known that one can build a Sequencer arbiter using an RGD arbiter (in addition to other components well known in the art) and vice versa.
Basic to most forms of arbiter is a mutual exclusion (ME) element. The mutual exclusion element is a circuit that executes the RGD arbiter function using a particular communication protocolxe2x80x94four-phase, return to zero signaling. A mutual exclusion element for a two-channel arbiter has two input terminals and two output terminals, with one input terminal and one output terminal associated with each channel. For the first channel, a rising transition on its input terminal signifies request, R1, and a falling transition on that same terminal signifies Done, D1. The ME element signals a corresponding grant with a rising transition on its G1 output channel. A falling transition on the G1 output channel has no significance. Thus, the mutual exclusion element is an RGD arbiter with a particular encoding of communication signals. Mutual exclusion elements commonly form the basis for RGD and Sequencer arbiters that use other communication protocols. The mutual exclusion element is not only a basis for RGD and Sequencer arbiters, but is also useful as a basic element in synchronizers. A synchronizer captures the value of an external signal for use in a synchronous system, ensuring that the captured form of the external signal remains stable during the interval in each clock cycle during which stability is required. The art of designing synchronizers and mutual exclusion elements is well known. See, for example, xe2x80x9cIntroduction to VLSI Systemsxe2x80x9d, Chapter 7 [FIG. 7.25 and pages 260-61 in particular] (1980), which is incorporated herein by reference for all purposes.
Arbiters are used to make choices that depend upon the order in which requests reach the arbiter. For example, arbiters can be used to implement a xe2x80x9cfirst-come, first-servedxe2x80x9d policy for sequencing access to a common resource. In a typical implementation, a second requester will not be issued a grant signal until service of a first grant to a first requester is complete, as indicated by the receipt of a Done signal.
The behavior of the Sequencer arbiter shown in FIG. 1 can be represented by the eight-state diagram shown in FIG. 2. State 1 is the initial state, which is indicated by using a circle that is thicker than those representing other states. The state of the arbiter changes based on signals it receives and signals it issues. For example, if a request is received on R1, there is a transition to state 2; or if a request is received on R2, there is a transition to state 3. A grant can be issued from three of the four upper-level of states (2, 3, 4), which results in a transition to one of the lower-level states (5, 6, 7). If a Done signal, D, is received when in one of the lower-level states, the arbiter xe2x80x9ctransitionsxe2x80x9d to an upper-level state. A state transition is designated here by the notation xe2x80x9cxe2x86x92xe2x80x9d between two state labels. For example, xe2x80x9c1xe2x86x922xe2x80x9d refers to the transition from state 1 to state 2. Using this notation, the transitions which can result from receipt of request signal R1 are 1xe2x86x922, 3xe2x86x924, 5xe2x86x926 and 7xe2x86x928; and for R2 are 1xe2x86x923, 2xe2x86x924, 5xe2x86x927 and 6xe2x86x928. The transitions which can result following a grant signal G1 are 2xe2x86x925 and 4xe2x86x927; and following a grant signal G2, are 3xe2x86x925 and 4xe2x86x926. The transitions resulting from a Done signal being received are 5xe2x86x921, 6xe2x86x922, 7xe2x86x923 and 8xe2x86x924. The arbitration function of the arbiter is only needed when the arbiter is in state 4; i.e., where the arbiter has received both an R1 and an R2 signal and must decide whether to issue a G1 grant or a G2 grant.
FIG. 3 is a projection of the state diagram of FIG. 2 onto the alphabet {G1, G2, D}. This state diagram has two states labeled xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d. The state numbers xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d have been chosen such that they also represent the number of grant signals which can be issued when the arbiter is in that state. Thus the Done signal D from state xe2x80x9c0xe2x80x9d to state xe2x80x9c1xe2x80x9d changes the number of grants that the arbiter is permitted to issue from 0 to 1. In other words: in state 0, no grant signals can be issued until a Done signal is received. The Done signal results in a transition to state 1, wherein one grant signal either G1 or G2xe2x80x94can be issued, resulting in a transition back to state 0. According to the convention established in FIG. 2, state 1 is the initial state.
As can be seen in the state diagrams of FIGS. 2-3, conventional arbiters require a Done signal following a grant signal before a second grant signal can be issued. This is an undesirable constraint when the common resource whose requests for access are being arbitrated can frequently handle more than one access concurrently, but occasionally can handle only a single access at a time.
U.S. Pat. No. 5,638,009 issued to Sutherland (hereinafter xe2x80x9cSutherlandxe2x80x9d; that patent is incorporated by reference herein for all purposes) teaches arbiters adapted to operate using a Three-wire event encoding scheme that, in a way, allows an arbiter to handle receipt of two Done events without an intervening grant signal. However, such an arbiter is limited to storing only one Done event when this Three-wire signaling protocol is used. More generally, such an arbiter that uses an N-wire signaling protocol can store Nxe2x88x921 Done events as pending signals on the Done input wires. Such an approach to storing Done events is limited, since N-wire signaling with N greater than 3 is complex, because the size of the arbiter increases as N2. In most applications, single-wire signaling is sufficient, and even Three-wire signaling uses much more logic and results in slower speed and greater design effort going into the circuit than is necessary.
Embodiments of a Sharing arbiter according to the present invention provide a technique and a system for issuing grants in response to requests where more than one grant is allowed to be outstanding at one time, representing a situation in which a resource can be accessedxe2x80x94in some casesxe2x80x94by more than one user.
In a specific embodiment, the Sharing arbiter is implemented by a Sequencer arbiter and a queue coupled to the Done input of the Sequencer arbiter. For an N-Sharing arbiter, i.e., one that allows up to, but no more than, N grants to be outstanding at one time, the queue has Nxe2x88x921 stages. Optionally, a Done Acknowledge output signal is provided to give external confirmation that a Done signal has been accepted by the queue. The queue can be preloaded with one or more Done signals if desired. A Sharing arbiter can, under certain conditions, act as a conventional arbiter and can have at most one grant outstanding while, under other conditions when its environment permits by sending the arbiter additional Done signals, it can issue more than one grant concurrently and thus can have more than one grant outstanding.
One application of the Sharing arbiter is to control accesses to a multi-port process, such as a dual-port memory. More generally, in this application, the Sharing arbiter is arbitrating access from multiple users to a single resource (or from multiple users to a plurality of resources that are contended for among the multiple users). Another application of the Sharing arbiter is to control task assignments from a task source to a plurality of processors or other task handlers. More generally, in this application, the Sharing arbiter is efficiently allocating objects among multiple recipients of those objects.
The Sharing arbiter is an arbiter which, under certain conditions, permits two or more Done signals to be received before issuing a grant signal and, under certain conditions, the Sharing arbiter is permitted to issue more than one grant signal before receiving a Done signal. If the Sharing arbiter has a Sharing-number N and K request inputs, and M input requests have been received (where Mxe2x89xa6K and Mxe2x89xa6N), and if P (where Pxe2x89xa7M) Done signals have also been received, the Sharing arbiter is permitted to issue M grant signals concurrently without enforcing mutual exclusion between the grants. If P Done signals have been received, and P less than M, then the Sharing arbiter arbitrates among the M input requests and is permitted to issue up to P grant signals concurrently.